package homework.day04;

import java.util.Arrays;

/**
 * @author ThinkBook
 */
public class Test10 {
    //冒泡排序
    public static void bubbleSort(int[] arr) {
        int len = arr.length;
        for(int i = 1; i < len; i++) {
            //如何实现 8|7 移动无序序列最后位置
            for(int j = 0; j < len-i; j++) {
                //比较相邻的两个元素并交换值：大的放后面，小的放前面
                if(arr[j] > arr[j+1]) {
                    arr[j] = arr[j] ^ arr[j+1];
                    arr[j+1] = arr[j] ^ arr[j+1];
                    arr[j] = arr[j] ^ arr[j+1];
                }
            }
            System.out.println("冒泡排序："+ Arrays.toString(arr));

        }
    }
    //选择排序
    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
//内层循环找到当前无序列表中最小下标
            for(int j = i + 1; j < arr.length; j++) {
                if(arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
//将无需列表中最小值添加到 有序列表最后位置
            if(minIndex != i) {
                arr[minIndex] = arr[minIndex] ^ arr[i];
                arr[i] = arr[minIndex] ^ arr[i];
                arr[minIndex] = arr[minIndex] ^ arr[i];
            }
            System.out.println("选择排序："+ Arrays.toString(arr));
        }

    }
    //插入排序
    public static void insertSort(int[] arr) {
        int len = arr.length;
        if(len <= 1) {
            return;
        }
//外层循环控制 总体循环次数
        for(int i = 1; i < len; i++) {
//内层循环做的事情：将无序列表中第一个元素插入到有序列表中合适位置
            int value = arr[i];
//获取有序列表中最后一个元素下标
            int j = i - 1;
            for(; j >= 0; j--) {
                if(value < arr[j]) {
                    arr[j+1] = arr[j];
                }else {
                    break;
                }
            }
//将需要插入的元素 放置到合适位置
            arr[j+1] = value;
//一次排序完成后，输出 方便 观察
            System.out.println("插入排序："+Arrays.toString(arr));
        }
    }


    public static void main(String[] args) {
        int[] arr = {56,34,45,12,67,52,4};
            bubbleSort(arr);
        int[] arr2 = {56,34,45,12,67,52,4};
            selectionSort(arr2);
        int[] arr3 = {56,34,45,12,67,52,4};
            insertSort(arr3);
    }
}
